/* vim: ft=c */
#ifndef PQUEUE_INCLUDED
#define PQUEUE_INCLUDED
/******************************************************************************
* (c)2025 Michael T. Richter
*
* This software is distributed under the terms of WTFPLv2.  The full terms and
* text of the license can be found at http://www.wtfpl.net/txt/copying
******************************************************************************/

/** @file
 *  @brief Implementation of a pqueue data structure.
 */

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#ifdef DEFAULT_PRIORITY_TYPE
typedef DEFAULT_PRIORITY_TYPE pri_t;
#else
typedef size_t pri_t;
#endif

/*
** Error codes.
*/
typedef enum pqueue_err_t
{
    PQ_OK  = 0,      /* successful operation             */
    PQ_RESIZE_ERR,   /* resizer failure                  */
    PQ_EMPTY_HEAP,   /* trying to remove from empty heap */
} pqueue_err_t;

/*
** A pqueue is a heap of these nodes.
*/
typedef struct pqueue_node_t
{
    pri_t  priority;
    void  *data;
} pqueue_node_t;

/*
** A user can manually manage node allocation and lifespans.  To do this they
** must pass in a pqueue_node_t array of appropriate size and supply a resizer
** function that fits this prototype.  (If the nodes are not to be grown, then
** the resizer function can just return NULL.)
*/
typedef pqueue_node_t *(*pqueue_resizer_t)(pqueue_node_t *nodes, size_t size);

/*
** The heap itself has this type.  Note that if you have provided the nodes you
** must ALSO provide the resizer.  There's no mixing and matching.
*/
typedef struct pqueue_heap_t
{
    bool              dynamic_heap;  /* heap lifespan is user-managed */
    bool              dynamic_nodes; /* node lifespan is user-managed */
    size_t            length, size;
    pqueue_resizer_t  resizer;       /* the resizer callback          */
    pqueue_node_t    *nodes;         /* the actual array of nodes     */
} pqueue_heap_t;

/*
** Detailed pqueue creation, explicitly indicating the heap, nodes, size, and
** resizing function.  NULL means that pqueue manages that entity.  Note again
** that if you supply one of nodes or resizer, you must provide both.
*/
pqueue_heap_t *pqueue_create_ex(pqueue_heap_t *heap, pqueue_node_t *nodes, size_t size, pqueue_resizer_t resizer);

/*
** A simple creation function wrapper for the most common likely use case.
*/
inline pqueue_heap_t *pqueue_create(size_t size)
{
    return pqueue_create_ex(NULL, NULL, size, NULL);
}

/*
** Insert data of a given priority into a priority queue.
*/
pqueue_err_t pqueue_insert(pqueue_heap_t *h, pri_t priority, void *data);

/*
** View the top node in the heap, NULL on failure.
*/
inline pqueue_node_t *pqueue_peek(const pqueue_heap_t *h)
{
    return ((h == NULL) || h->length == 0) ? NULL : &h->nodes[0];
}

/*
** Remove the top node in the heap, placing it into node.
*/
pqueue_err_t pqueue_remove(pqueue_heap_t *h, pqueue_node_t *node);

/*
** Safely clean up a heap regardless of which items are dynamic and which
** are user-supplied.  User-supplied members must be manually cleaned up.
** Note that if resized, the nodes member may differ from what what was
** passed in, so clean from the structure, not from the original parameters.
*/
void pqueue_destroy(pqueue_heap_t **h);

#ifdef PQUEUE_IMPLEMENTATION
/*******************************************************************************
* PQUEUE IMPLEMENTATION SECTION
* =================================
*
* In a single source file in your project, the symbol PQUEUE_IMPLEMENTATION
* must be defined before including the header:
*
*   ```c
*   #define PQUEUE_IMPLEMENTATION
*   #include "pqueue.h"
*   ```
*
* All other source files using this library must *not* define this symbol.
*******************************************************************************/
#ifdef DEBUG
#include <stdio.h>
#define DEBUG_OUT(F, ...) fprintf(stderr, F, __VA_ARGS__)
#else
#define DEBUG_OUT(F, ...)
#endif

pqueue_heap_t *pqueue_create_ex(pqueue_heap_t *heap, pqueue_node_t *nodes, size_t size, pqueue_resizer_t resizer)
{
    DEBUG_OUT("pqueue_create_ex(%p, %p, %u, %p)\n", heap, nodes, size, resizer);
    pqueue_heap_t *rv = NULL;

    if (((nodes != NULL) && (resizer == NULL))
     || ((nodes == NULL) && (resizer != NULL)))
    {
        /* we either manage it all or we manage none of it */
        rv = NULL;
    }
    else
    {
        rv = (heap == NULL) ? malloc(sizeof(pqueue_heap_t))
                                          : heap;
        if (rv != NULL)
        {
            rv->length        = 0;
            rv->size          = size;
            rv->resizer       = resizer;
            rv->nodes         = (nodes == NULL) ? malloc(sizeof(pqueue_node_t) * size) : nodes;
            rv->dynamic_heap  = (heap == NULL);
            rv->dynamic_nodes = (nodes == NULL);
            if (rv->nodes == NULL)
            {
                if (rv != heap)
                {
                    free(rv);
                    rv = NULL;
                }
            }
        }
    }
    DEBUG_OUT("pqueue_create_ex returning: rv = %p, "
                                          "rv->length = %u, "
                                          "rv->size = %u, "
                                          "rv->resizer = %p, "
                                          "rv->nodes = %p\n",
               rv, rv->length, rv->size, rv->resizer, rv->nodes);
    return rv;
}

__attribute__((noinline)) void pqueue_destroy(pqueue_heap_t **h)
{
    /*
    ** GCC insists on inlining this function, and then when it does it
    ** insists on whining about a guarded free specifically set up to
    ** ensure that which it is whining about **doesn't happen**.  So
    ** we have to do the weird shit with attributes and diagnostics
    ** together to get it to shut the fuck up.
    */
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
    if ((*h)->dynamic_nodes)
    {
        free((*h)->nodes);
    }

    bool cleanup = (*h)->dynamic_heap;
    memset(*h, 0, sizeof(pqueue_heap_t));

    if (cleanup)
    {
        free(*h);
    }
    *h = NULL;
#pragma GCC diagnostic pop
}

pqueue_err_t pqueue_insert(pqueue_heap_t *h, pri_t priority, void *data)
{
    DEBUG_OUT("pqueue_insert(%p, %u, %p)\n", h, priority, data);
    pqueue_err_t rv = PQ_OK;

    /* we're growing too big */
    if ((h->length) >= (h->size))
    {
        /* double our node capacity */
        h->nodes = (h->resizer == NULL) ? realloc(h->nodes, h->size * 2 * sizeof(pqueue_node_t))
                                        : h->resizer(h->nodes, h->size * 2 * sizeof(pqueue_node_t));
        if (h->nodes == NULL)
        {
            // the resizer failed
            rv = PQ_RESIZE_ERR;
            return rv;
        }
        else
        {
            h->size *= 2;
        }
    }

    if (rv != PQ_OK)
    {
        return rv;
    }

    size_t i = h->length;
    size_t j = i / 2;

    while ((i > 0) && (h->nodes[j].priority > priority))
    {
        h->nodes[i] = h->nodes[j];
        i = j;
        j = j / 2;
    }

    h->nodes[i].priority = priority;
    h->nodes[i].data = data;
    h->length++;

    return rv;
}

pqueue_err_t pqueue_remove(pqueue_heap_t *h, pqueue_node_t *n)
{
    DEBUG_OUT("pqueue_remove(%p, %p)\n", h, n);
    if ((h == NULL) || (h->length == 0))
    {
        DEBUG_OUT("returning: %s\n", "PQ_EMPTY_HEAP");
        return PQ_EMPTY_HEAP;
    }

    *n = h->nodes[0];

    size_t i, j, k;
    h->nodes[0] = h->nodes[h->length--];

    i = 0;
    while (i != h->length)
    {
        k = h->length;
        j = 2 * i + 1;

        if (j < h->length && h->nodes[j].priority < h->nodes[k].priority)
        {
            k = j;
        }

        if (j + 1 < h->length && h->nodes[j + 1].priority < h->nodes[k].priority)
        {
            k = j + 1;
        }

        h->nodes[i] = h->nodes[k];
        i = k;
    }

    DEBUG_OUT("returning: %s\n", "PQ_OK");
    return PQ_OK;
}

#endif //PQUEUE_IMPLEMENTATION
#endif //PQUEUE_INCLUDED

#if 0
char *pop (heap_t *h) {
    int i, j, k;
    if (!h->len) {
        return NULL;
    }
    char *data = h->nodes[1].data;

    h->nodes[1] = h->nodes[h->len];

    h->len--;

    i = 1;
    while (i!=h->len+1) {
        k = h->len+1;
        j = 2 * i;
        if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) {
            k = j;
        }
        if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) {
            k = j + 1;
        }
        h->nodes[i] = h->nodes[k];
        i = k;
    }
    return data;
}

int main () {
    heap_t *h = (heap_t *)calloc(1, sizeof (heap_t));
    push(h, 3, "Clear drains");
    push(h, 4, "Feed cat");
    push(h, 5, "Make tea");
    push(h, 1, "Solve RC tasks");
    push(h, 2, "Tax return");
    int i;
    for (i = 0; i < 5; i++) {
        printf("%s\n", pop(h));
    }
    return 0;
}
#endif
